package com.sl.leetcode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by lisulong on 2019/9/11.
 * 例如，给定数组 nums = [-1,0,1,2,-1,-4]
 * 输出
 * [
 * [-1,0,1]
 * [-1,-1,2]
 * ]
 */
public class Solution15ThreeSum {
    @Test
    public void main() {
        threeSum(new int[]{-1, 0, 1, 2, -1, -4});
        threeSum(new int[]{1, 1, 1});
        threeSum(new int[]{-2, 0, 0, 2, 2});
        threeSum(new int[]{0, 0, 0});
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);//使用的快排，问题：快排的原理
        int last, first;
        int tempSum;
        if (nums[0] <= 0 && nums[nums.length - 1] >= 0) {// 优化1: 整个数组同符号，则无解
            for (int i = 0; i < nums.length - 2; i++) {
                if (nums[i] > 0) break;// 优化2: 最左值为正数则一定无解
                if (i != 0 && nums[i] == nums[i - 1]) continue;// 优化3: 主指针当前值和上一个值一样，则指针继续后移
                first = i + 1;//遍历指针后面的指针
                last = nums.length - 1;//尾巴指针
                
                while (last > first) {
                    tempSum = nums[i] + nums[last] + nums[first];
                    if (tempSum > 0) {
                        last = leftMoveIndex(nums, first, last);
                    } else if (tempSum < 0) {
                        first = rightMoveIndex(nums, first, last);
                    } else if (tempSum == 0) {
                        List<Integer> subResult = Arrays.asList(nums[i], nums[last], nums[first]);
                        result.add(subResult);
                        last = leftMoveIndex(nums, first, last);
                        first = rightMoveIndex(nums, first, last);
                    }
                }
            }
        }
        return result;
    }
    //优化版
    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);//使用的快排，问题：快排的原理
        int last, first;
        int tempSum;
        if (nums[0] <= 0 && nums[nums.length - 1] >= 0) {// 优化1: 整个数组同符号，则无解
            for (int i = 0; i < nums.length - 2; i++) {
                if (nums[i] > 0) break;// 优化2: 最左值为正数则一定无解
                if (i != 0 && nums[i] == nums[i - 1]) continue;// 优化3: 主指针当前值和上一个值一样，则指针继续后移
                first = i + 1;//遍历指针后面的指针
                last = nums.length - 1;//尾巴指针

                while (last > first) {
                    tempSum = nums[i] + nums[last] + nums[first];
                    if (tempSum == 0) { // 如果可以组队
                        result.add(Arrays.asList(nums[i], nums[last], nums[first]));
                    }
                    if (tempSum <= 0 ) { // 实力太弱，把菜鸟那边右移一位
                        while (first < last && nums[first] == nums[++first]){} // 如果相等就跳过
                    } else { // 实力太强，把大神那边右移一位
                        while (first < last && nums[last] == nums[--last]) {}
                    }
                    
                    if (tempSum > 0) {
                        last = leftMoveIndex(nums, first, last);
                    } else if (tempSum < 0) {
                        first = rightMoveIndex(nums, first, last);
                    } else if (tempSum == 0) {
                        List<Integer> subResult = Arrays.asList(nums[i], nums[last], nums[first]);
                        result.add(subResult);
                        last = leftMoveIndex(nums, first, last);
                        first = rightMoveIndex(nums, first, last);
                    }
                }
            }
        }
        return result;
    }
    private int rightMoveIndex(int[] nums, int lIndex, int rIndex) {
        do {
            lIndex++;
        } while (nums[lIndex] == nums[lIndex - 1] && rIndex > lIndex);
        return lIndex;
    }

    private int leftMoveIndex(int[] nums, int lIndex, int rIndex) {
        do {
            rIndex--;
        } while (nums[rIndex] == nums[rIndex + 1] && rIndex > lIndex);
        return rIndex;
    }
}
